package tree;

import java.util.*;
import java.util.stream.Collector;
//001011111001111011010111110011110110101111100111101101011000101000110101110001001010000100111001011010110001010001101
public class huffmanTree {
    public static void main(String[] args) {
        String s="123456789";
        s=s.substring(s.length()-6);
        System.out.println(s);
      /*  int[] arr = new int[]{1,2,3,4
        };
        Node node = haffman(arr);
        node.pre();*/

    }


public static  Node haffman(int[] arr){
    List<Node> list = new ArrayList<Node>();
    for(int a:arr){
        list.add(new Node(a));
    }
Collections.sort(list);
//    ;
    while (list.size()>1){
        Collections.sort(list);

    Node left = list.get(0);
    Node right = list.get(1);
        Node on= new Node(left.value+right.value);
     on.left=left;
     on.right=right;
    list.remove(0);
    list.remove(1);
    list.add(on);
    on.pre();
    }
    return list.get(0);


}
}
class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;
    Node(int value){
        this.value=value;
    }
    public void pre(){
        System.out.println(this);
        if(this.left!=null){
            this.left.pre();
        }

        if(this.right!=null){
            this.right.pre();
        }
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node n) {
        return value-n.value ;
    }
}